1. Field of the Invention
The present invention relates to the representation of curves in graphics systems and, in particular, describes a methods by which objects described by cubic polynomials can be converted into corresponding quadratic polynomial descriptions.
2. Description of the Related Art
Computerised graphics systems generally form an image based upon one or more graphic objects, each defining a particular shape, component or line in the image. Typically, each object is defined by an outline curve which defines the interior of the object which can be displayed, by varying the colour between the interior and the exterior of the outline curve the outline curve can itself define a portion of an objects structure.
One popular form of defining the outline of each object is a spline format and the most popular spline formats are various forms for parametric cubic polynomials, such as Bezier curves. Other types of cubic polynomials that can be used are Hermite and B-splines.
Although cubic polynomials have been used for a number of years to produce high quality graphic images, such images take a substantial time to calculate and display in view of the need to calculate the roots of a cubic polynomial in order to obtain the various pixel locations of the curve outline on each scan-line of the display, such as a video display unit or a printer.
Although current levels of technology are sufficient to produce hardware able to perform the necessary calculations required to display cubic polynomials in real-time for full video animation, such hardware is highly complex, expensive and therefore not readily accessible to consumer markets.
Reference is hereby made to the following patent specifications lodged concurrently herewith and the disclosure of which is hereby incorporated by cross-reference:
(i) U.S. patent application Ser. No. 08/053,373, filed Apr. 28, 1993, claiming priority from Australian Patent Application No. PL2147, filed Apr. 29, 1992, entitled "A Real-Time Object Based Graphics System"; PA1 (iv) U.S. patent application Ser. No. 08/053,363, filed Apr. 28, 1993, claiming priority from Australian Patent Application No. PL 2156, filed Apr. 29, 1992, entitled "Edge Calculation for Graphics Systems"; PA1 (v) U.S. patent application Ser. No. 08/053,378, filed Apr. 28, 1993, claiming priority from Australian Patent Application No. PL 2142, filed Apr. 29, 1992, entitled: "A Preprocessing Pipeline for RTO Graphics System"; PA1 (vi) U.S. patent application Ser. No. 08/053,231 claiming priority from Australian Patent Application No. PL 2145 Apr. 29, 1992, entitled "Object Sorting for Graphics Systems"; and PA1 (vii) U.S. patent application Ser. No. 08/053,219, filed Apr. 28, 1993, claiming priority from Australian Patent Application No. PL 2150, filed Apr. 29, 1992, entitled "Object Based Graphics Using Quadratic Polynomial Fragments". PA1 PIXEL (line.sub.n+1)=PIXEL (line.sub.n)+.DELTA.PIXEL (line.sub.n) PA1 .DELTA.PIXEL (line.sub.n+1)=.DELTA.PIXEL (line.sub.n)+.DELTA..DELTA.PIXEL PA1 where PA1 PIXEL (line.sub.n =START.sub.-- LINE)=START.sub.-- PIXEL; and PA1 .DELTA.PIXEL (line.sub.n =START.sub.-- LINE)=.DELTA.PIXEL. PA1 (a). selecting start and end points on said spline and designating same as corresponding start and end points on the corresponding QPF; PA1 (b). determining from the control points of the spline, coefficients of the quadratic polynomial describing said QPF; PA1 (c). using the coefficients to determine if an error between the spline and the quadratic polynomial is below a predetermined level; and PA1 (d). if so, determining from said coefficients, QPF data describing said quadratic polynomial. PA1 (e). the spline is divided into two or more sub-splines for which a corresponding quadratic polynomial is determined. This step is repeated if necessary until the error between each quadratic polynomial and the corresponding sub-spline is below the predetermined amount. The error can be an area error and/or an angle error. PA1 (a). selecting start and end points on said spline and designating same as corresponding start and end points for a plurality of QPF's on the corresponding QPF; PA1 (b). determining from the control points of the spline, coefficients of the quadratic polynomial describing each said QPF; PA1 (c). using the coefficients to determine if an error between the spline and the quadratic polynomials is below a predetermined level; and PA1 (d) if so, determining from said coefficients, QPF data describing said quadratic polynomials. PA1 (e). the spline is divided into two or more sub-splines for which a corresponding quadratic polynomial(s) is determined using steps (a) to (d) from either the first or second aspect. This step is repeated if necessary until the area error between each quadratic polynomial and the corresponding sub-spline is below the predetermined amount. PA1 determining a set of equations with corresponding variable values describing an error associated with the said splines and their corresponding QPFs, and PA1 optimizing said set of equations to determine a best set of variable values. PA1 (a) selecting a first spline of said closed loop and with said first spline: PA1 (b) with all the intermediate splines in said closed loop: PA1 (c) with a final spline in said closed loop
In the above specifications it is proposed to use an alternative format for the representation of curve outline. Instead of using cubic polynomials, and cubic splines in particular, it is proposed to use quadratic polynomial fragments (QPF's). QPF's, in view of their representation being based upon quadratic polynomials as opposed to cubic polynomials, can be more easily calculated, preferably by two separate additions, and thereby permit the real-time calculation and rendering of object based images.
In this manner, a graphic object can be divided into a plurality of QPF's which define various portions of the object outline and from which the object edges can be calculated prior to display of the image.
As specifically described in Australian Patent Application No. PL 2150, filed Apr. 29, 1992, entitled "Object Based Graphics Using Quadratic Polynomial Fragments", a QPF can be described by the following QPF data components: START.sub.-- PIXEL, .DELTA.PIXEL, .DELTA..DELTA.PIXEL, START.sub.-- LINE, and END.sub.-- LINE. In this manner, such QPF data can be used to generate pixel location values (PIXEL) along the QPF between the START.sub.-- LINE and END.sub.-- LINE in the following manner:
Because there currently exists large numbers of graphic objects described by cubic polynomials such as Bezier splines, it is desirable that a means be provided by which objects described in known spline formats can be converted into QPF's.